{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10-1 Comparisons among lists\n",
    "\n",
    "> For each of the four types of lists in the following table, what is the asymptotic worst-case running time for each dynamic-set operation listed?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| |unsorted, singly linked|sorted, singly linked|unsorted, doubly linked|sorted, doubly linked|\n",
    "|:-:|:-:|:-:|:-:|:-:|\n",
    "|SEARCH$(L,k)$|$\\Theta(n)$|$\\Theta(n)$|$\\Theta(n)$|$\\Theta(n)$|\n",
    "|INSERT$(L,x)$|$\\Theta(1)$|$\\Theta(n)$|$\\Theta(1)$|$\\Theta(n)$|\n",
    "|DELETE$(L,x)$|$\\Theta(n)$|$\\Theta(n)$|$\\Theta(1)$|$\\Theta(1)$|\n",
    "|SUCCESSOR$(L,x)$|$\\Theta(n)$|$\\Theta(1)$|$\\Theta(n)$|$\\Theta(1)$|\n",
    "|PREDECESSOR$(L,x)$|$\\Theta(n)$|$\\Theta(n)$|$\\Theta(n)$|$\\Theta(1)$|\n",
    "|MINIMUM$(L)$|$\\Theta(n)$|$\\Theta(1)$|$\\Theta(n)$|$\\Theta(1)$|\n",
    "|MAXIMUM$(L)$|$\\Theta(n)$|$\\Theta(n)$|$\\Theta(n)$|$\\Theta(n)$|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10-2 Mergeable heaps using linked lists\n",
    "\n",
    "> A mergeable heap supports the following operations: MAKE-HEAP (which creates an empty mergeable heap), INSERT, MINIMUM, EXTRACT-MIN, and UNION. Show how to implement mergeable heaps using linked lists in each of the following cases. Try to make each operation as efficient as possible. Analyze the running time of each operation in terms of the size of the dynamic set(s) being operated on."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*a*__. Lists are sorted."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "MAKE-HEAP $\\Theta(1)$, INSERT $\\Theta(n)$, MINIMUM $\\Theta(1)$, EXTRACT-MIN $\\Theta(1)$, UNION $\\Theta(n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedListNode:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "class MergeableHeap:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def to_list(self):\n",
    "        values = []\n",
    "        x = self.head\n",
    "        while x is not None:\n",
    "            values.append(x.value)\n",
    "            x = x.next\n",
    "        return values\n",
    "\n",
    "    def insert(self, value):\n",
    "        new_node = LinkedListNode(value)\n",
    "        if self.head is None:\n",
    "            self.head = new_node\n",
    "        else:\n",
    "            if value < self.head.value:\n",
    "                new_node.next = self.head\n",
    "                self.head = new_node\n",
    "            else:\n",
    "                x = self.head\n",
    "                while x.next is not None and x.next.value < value:\n",
    "                    x = x.next\n",
    "                if x.next is None or x.next < value:\n",
    "                    new_node.next = x.next\n",
    "                    x.next = new_node\n",
    "\n",
    "    def minimum(self):\n",
    "        if self.head is None:\n",
    "            return None\n",
    "        return self.head.value\n",
    "\n",
    "    def extract_min(self):\n",
    "        if self.head is None:\n",
    "            return None\n",
    "        x = self.head.value\n",
    "        self.head = self.head.next\n",
    "        return x\n",
    "\n",
    "    def union(self, other):\n",
    "        head = LinkedListNode(None)\n",
    "        x = head\n",
    "        while self.head is not None or other.head is not None:\n",
    "            if other.head is None:\n",
    "                x.next = self.head\n",
    "                self.head = self.head.next\n",
    "            elif self.head is None:\n",
    "                x.next = other.head\n",
    "                other.head = other.head.next\n",
    "            elif self.head.value <= other.head.value:\n",
    "                x.next = self.head\n",
    "                self.head = self.head.next\n",
    "            else:\n",
    "                x.next = other.head\n",
    "                other.head = other.head.next\n",
    "            if x.next.value != x.value:\n",
    "                x = x.next\n",
    "        x.next = None\n",
    "        self.head = head.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*b*__. Lists are unsorted."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "MAKE-HEAP $\\Theta(1)$, INSERT $\\Theta(1)$, MINIMUM $\\Theta(n)$, EXTRACT-MIN $\\Theta(n)$, UNION $\\Theta(n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedListNode:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "class MergeableHeap:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def to_list(self):\n",
    "        values = []\n",
    "        x = self.head\n",
    "        while x is not None:\n",
    "            values.append(x.value)\n",
    "            x = x.next\n",
    "        return values\n",
    "\n",
    "    def insert(self, value):\n",
    "        x = LinkedListNode(value)\n",
    "        if self.head is None:\n",
    "            self.head = x\n",
    "        else:\n",
    "            x.next = self.head\n",
    "            self.head = x\n",
    "\n",
    "    def minimum(self):\n",
    "        if self.head is None:\n",
    "            return None\n",
    "        min_val = self.head.value\n",
    "        x = self.head.next\n",
    "        while x is not None:\n",
    "            min_val = min(min_val, x.value)\n",
    "            x = x.next\n",
    "        return min_val\n",
    "\n",
    "    def delete(self, value):\n",
    "        prev = None\n",
    "        x = self.head\n",
    "        while x is not None:\n",
    "            if x.value == value:\n",
    "                if x == self.head:\n",
    "                    self.head = self.head.next\n",
    "                prev.next = x.next\n",
    "            prev = x\n",
    "            x = x.next\n",
    "\n",
    "    def extract_min(self):\n",
    "        x = self.minimum()\n",
    "        self.delete(x)\n",
    "        return x\n",
    "\n",
    "    def union(self, other):\n",
    "        if self.head is None:\n",
    "            self.head = other.head\n",
    "        else:\n",
    "            x = self.head\n",
    "            while x.next is not None:\n",
    "                x = x.next\n",
    "            x.next = other.head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*c*__. Lists are unsorted, and dynamic sets to be merged are disjoint."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Same as __*b*__."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10-3 Searching a sorted compact list\n",
    "\n",
    "> __*a*__. Suppose that COMPACT-LIST-SEARCH$(L, n, k)$ takes $t$ iterations of the while loop of lines 2–8. Argue that COMPACT-LIST-SEARCH'$(L, n, k, t)$ returns the same answer and that the total number of iterations of both the for and while loops within COMPACT-LIST-SEARCH' is at least $t$.\n",
    "\n",
    "> __*b*__. Argue that the expected running time of COMPACT-LIST-SEARCH'$(L, n, k, t)$ is $O(t+\\text{E}[X_t])$.\n",
    "\n",
    "> __*c*__. Show that $\\text{E}[X_t] \\le \\sum_{r=1}^n (1-r/n)^t$.\n",
    "\n",
    "> __*d*__. Show that $\\sum_{r=0}^{n-1} r^t \\le n^{t+1}/(t+1)$.\n",
    "\n",
    "> __*e*__. Prove that $\\text{E}[X_t] \\le n/(t+1)$.\n",
    "\n",
    "> __*f*__. Show that COMPACT-LIST-SEARCH'$(L, n, k, t)$ runs in $O(t+n/t)$ expected time.\n",
    "\n",
    "> __*g*__. Conclude that COMPACT-LIST-SEARCH runs in $O(\\sqrt{n})$ expected time.\n",
    "\n",
    "> __*h*__. Why do we assume that all keys are distinct in COMPACT-LIST-SEARCH? Argue that random skips do not necessarily help asymptotically when the list contains repeated key values."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
